这是前两天10级排位赛数据结构场的题，当时看了没思路就没去做，这两天在学线段树的时候又想到了这道题，拿来一看这么简单。。。
题意：n个女孩参加舞会，每个女孩有三个属性，如果一个女孩发现有人三项属性都高于自己，她就伤心的跳楼了。。给出n和每个人的属性，问最后有多少人跳楼。
思路：有点类似求逆序数。每个属性的范围是10^9，离散化是必须的了。翅膀先说说自己的做法，其实三个属性都一样的，操作的时候可以任意选取。记三个属性为x、y、z，先按y升序排序，然后给y标号，y相同就标相同的号，标号就是为了离散化～然后按x降序排序，以y为坐标，z为关键字，每次查询区间最大值进行比较、更新即可。可用线段树或树状数组解决。
注意：一个人发现有人比自己强就跳楼了，不要重复统计，不能让人家一直跳楼吧（信春哥，原地满血满状态复活？？？）
线段树版本：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
/*
algorithm : segment tree
Memory 15100K Time 1170MS Language G++
code by : zhyu
*/
#include
#include
#include
using
namespace
std;
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,l,h) for(int i=(l);i<=(h);++i)
#define FORD(i,h,l) for(int i=(h);i>=(l);--i)
#define N 500010
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1 | 1
int
tree[N<<2];
struct
node
{
int
x,y,z;
}a[N];
bool
cmpy(node a,node b)
{
return
a.y}
bool
cmpx(node a,node b)
{
if
(a.x==b.x)
{
if
(a.y!=b.y)
return
a.y>b.y;
return
a.z>b.z;
}
return
a.x>b.x;
}
void
PushUp(
int
rt)
{
tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}
void
build(
int
l,
int
r,
int
rt)
{
tree[rt]=-1;
if
(l==r)
return
;
int
m=(l+r)>>1;
build(lson);
build(rson);
}
void
update(
int
p,
int
val,
int
l,
int
r,
int
rt)
{
if
(l==r)
{
tree[rt]=max(tree[rt],val);
return
;
}
int
m=(l+r)>>1;
if
(p<=m) update(p,val,lson);
else
update(p,val,rson);
PushUp(rt);
}
int
query(
int
L,
int
R,
int
l,
int
r,
int
rt)
{
if
(L>r)
return
-1;
if
(l>=L && r<=R)
return
tree[rt];
int
m=(l+r)>>1;
int
res=0;
if
(L<=m) res=max(res,query(L,R,lson));
if
(R>m) res=max(res,query(L,R,rson));
return
res;
};
int
main(
void
)
{
int
n;
scanf
(
"%d"
,&n);
FOR(i,1,n)
scanf
(
"%d"
,&a[i].x);
FOR(i,1,n)
scanf
(
"%d"
,&a[i].y);
FOR(i,1,n)
scanf
(
"%d"
,&a[i].z);
sort(a+1,a+n+1,cmpy);
int
pre=a[1].y;
a[1].y=1;
FOR(i,2,n)
{
int
tmp=a[i].y;
if
(a[i].y==pre) a[i].y=a[i-1].y;
else
a[i].y=a[i-1].y+1;
pre=tmp;
}
int
len=a[n].y;
sort(a+1,a+n+1,cmpx);
build(1,len,1);
int
ans=0;
int
i=1;
while
(i<=n)
{
int
j=i;
while
(j<=n && a[i].x==a[j].x)
{
if
(j<=n && query(a[j].y+1,len,1,len,1)>a[j].z) ans++;
j++;
}
j=i;
while
(j<=n && a[i].x==a[j].x)
{
update(a[j].y,a[j].z,1,len,1);
j++;
}
i=j;
}
printf
(
"%d\n"
,ans);
return
0;
}
|
树状数组版本：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
/*
algorithm : bit
Memory 9200K Time 920MS Language G++
code by : zhyu
*/
#include
#include
#include
using
namespace
std;
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,l,h) for(int i=(l);i<=(h);++i)
#define FORD(i,h,l) for(int i=(h);i>=(l);--i)
#define N 500010
#define lowbit(x) (x&(-x))
struct
node
{
int
x,y,z;
}a[N];
int
c[N];
int
n;
bool
cmpy(node a,node b)
{
return
a.y}
bool
cmpx(node a,node b)
{
if
(a.x==b.x)
{
if
(a.y==b.y)
return
a.z>b.z;
return
a.y>b.y;
}
return
a.x>b.x;
}
void
update(
int
x,
int
val)
{
while
(x>0)
{
if
(c[x]
x-=lowbit(x);
}
}
int
getmax(
int
x)
{
int
res=0;
while
(x<=n)
{
if
(c[x]>res) res=c[x];
x+=lowbit(x);
}
return
res;
}
int
main(
void
)
{
scanf
(
"%d"
,&n);
FOR(i,1,n)
scanf
(
"%d"
,&a[i].x);
FOR(i,1,n)
scanf
(
"%d"
,&a[i].y);
FOR(i,1,n)
scanf
(
"%d"
,&a[i].z);
sort(a+1,a+n+1,cmpy);
int
pre=a[1].y;
a[1].y=1;
FOR(i,2,n)
{
int
tmp=a[i].y;
if
(a[i].y==pre) a[i].y=a[i-1].y;
else
a[i].y=a[i-1].y+1;
pre=tmp;
}
sort(a+1,a+n+1,cmpx);
int
ans=0;
int
i=1;
while
(i<=n)
{
int
j=i;
while
(j<=n && a[i].x==a[j].x)
{
if
(getmax(a[j].y+1)>a[j].z) ans++;
j++;
}
j=i;
while
(j<=n && a[i].x==a[j].x)
{
update(a[j].y,a[j].z);
j++;
}
i=j;
}
printf
(
"%d\n"
,ans);
return
0;
}
|
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有